

		ORIGAMI - REZOLVARE
	       ---------------------

SOLUTIE 1:
----------
	O abordare  brute force ar cere mentinerea unei structuri de date ce descrie starea colii
de hartie de pe masa masinii. Desigur, zonele de o anumita grosime formeaza o reuniune de poligoa-
ne, prin urmare putem mentine o lista de perechi de forma (grosime,lista de poligoane) unde "lista
de poligoane" reprezinta lista zonelor colii in care avem "grosime" pliuri suprapuse.
	Initial avem deci o singura zona (un singur poligon) de grosime 1, si anume patratul (0,0,
100,100). La fiecare indoire trebuie sa facem urmatoarele operatii:
- determinam poligoanele "taiate" de linia de indoire si le descompunem in doua;
- oglindim poligoanele dintr-unul din semiplane in celalalt;
- intersectam poligoanele astfel suprapuse;
- pentru fiecare poligon rezultat din intersectie, calculam grosimea (numarul de pliuri) ca suma a
grosimilor poligoanelor din care provine.

SOLUTIE 2:
----------

	Solutia mai simpla provine de la observatia ca avem nevoie de grosimea origami-ului doar in
ounctele candidate pentru efectuarea perforatiei. Cum putem calcula grosimea intr-un astfel de
punct? Ne uitam la ultima indoire efectuata: daca punctul se afla in semiplanul dinspre care se fa-
ce indoirea, atunci grosimea este evident 0 (tocmai am pliat ce era acolo); daca punctul se afla
in semiplanul spre care se face indoirea, atunci pliurile din acel punct sunt cele dinainte de
indoire plus cele ce au venit in urma indoirii. Ca urmare, grosimea este grosimea initiala in acel
punct plus grosimea initiala in punctul simetric fata de linia de indoire. Bineinteles, initial
coala are grosimea 1 in interiorul patratului (0,0,100,100) si 0 in rest.
	Prin urmare, algoritmul este urmatorul:

var t:array of linie;	{ lista de indoiri}
    n:integer;        ( numarul de indoiri}

function grosime(p:punct;k:integer);
	{ calculeaza grosimea in punctul p, dupa primele k indoiri }
begin
if k=0 then if p in patrat(0,0,100,100) then grosime:=1
	    else grosime:=0
else if stanga(p,t[k])
then grosime:=grosime(p,k-1)+grosime(simetric(p,t[k]),k-1)
else grosime:=0;
end; 	